/* cdsl_rbtree.h - red-black tree
 * Copyright (c) 2009 Charles Wilson
 * This file is part of the C Data Structures Library.
 *
 * Derived from code released into the public domain by Julienne Walker:
 * http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
 *   > Created (Julienne Walker): August 23, 2003
 *   > Modified (Julienne Walker): March 14, 2008
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef CDSL_RBTREE_H
#define CDSL_RBTREE_H

#ifdef __cplusplus
#include <cstddef>

using std::size_t;

extern "C"
  {
#else
#include <stddef.h>
#endif

    /* Opaque types */
    typedef struct cdsl_rbtree cdsl_rbtree_t;
    typedef struct cdsl_rbtrav cdsl_rbtrav_t;

    /* User-defined item handling */
    typedef int   (*cdsl_rbtree_cmp_f) (const cdsl_rbtree_t* tree, const void *p1, const void *p2);
    typedef void *(*cdsl_rbtree_dup_f) (const cdsl_rbtree_t* tree, const void *p);
    typedef void  (*cdsl_rbtree_rel_f) (const cdsl_rbtree_t* tree, void *p);

    /* Red Black tree functions */
    cdsl_rbtree_t *cdsl_rbnew    (cdsl_rbtree_cmp_f cmp, cdsl_rbtree_dup_f dup, cdsl_rbtree_rel_f rel);
    void           cdsl_rbdelete (cdsl_rbtree_t *tree);
    void           cdsl_rbclear  (cdsl_rbtree_t *tree);
    void          *cdsl_rbfind   (cdsl_rbtree_t *tree, void *data);
    int            cdsl_rbinsert (cdsl_rbtree_t *tree, void *data);
    int            cdsl_rberase  (cdsl_rbtree_t *tree, void *data);
    size_t         cdsl_rbsize   (cdsl_rbtree_t *tree);

    /* Traversal functions */
    cdsl_rbtrav_t *cdsl_rbtnew    (void );
    void           cdsl_rbtdelete (cdsl_rbtrav_t *trav);
    void          *cdsl_rbtfirst  (cdsl_rbtrav_t *trav, cdsl_rbtree_t *tree);
    void          *cdsl_rbtlast   (cdsl_rbtrav_t *trav, cdsl_rbtree_t *tree);
    void          *cdsl_rbtnext   (cdsl_rbtrav_t *trav);
    void          *cdsl_rbtprev   (cdsl_rbtrav_t *trav);
    void          *cdsl_rbtdata   (cdsl_rbtrav_t *trav);

    /* other */
    void *cdsl_rb_getUD (const cdsl_rbtree_t *tree);
    void *cdsl_rb_setUD (      cdsl_rbtree_t *tree, void * userdata);

#ifdef __cplusplus
  }
#endif

#endif

